跳到主要内容

1139.最大的以 1 为边界的正方形

· 阅读需 3 分钟

1、题干​

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

 

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

 

提示：

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] 为 0 或 1

2、思路​

纯模拟，毫无技巧，全是感情🤡

遍历网格，以当前网格单元作为正方形左上顶点，先求出左上两条边长的最大可能值，再验证右下两条边是否满足要求。

优化代码又折腾了一番，速度得到一些提升，从最快 88ms 达到最快 68ms。

主要优化在于检查边长的时候，由于是正方形可以同时检查两条边。做法是固定起始位置，然后改变边长，两条边同时满足要求时才往下遍历。

3、代码​

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let len = 1;
            while (grid[i][j + len] && grid[i + len]?.at(j)) len++;

            for (; len > maxLen; len--) {
                let step = 1, ei = i + len - 1, ej = j + len - 1;
                while (step < len && grid[i + step][ej] && grid[ei][j + step]) step++;

                if (step === len) maxLen = len;
            }
        }
    }

    return maxLen ** 2;
};

下面是最开始的代码，可以对照看看

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let si = i + 1, sj = j + 1;
            while (si < m && grid[si]?.at(j)) si++;
            while (sj < n && grid[i][sj]) sj++;

            let len = Math.min(si - i, sj - j);
            for (; len > maxLen; len--) {
                let ei = i + len - 1, ej = j + len - 1;
                while (ei > i && grid[ei][j + len - 1]) ei--;
                while (ej > j && grid[i + len - 1][ej]) ej--;

                if (ei === i && ej === j) maxLen = Math.max(maxLen, len);
            }
        }
    }

    return maxLen ** 2;
};

4、复杂度​

  • 时间复杂度：最差O(n4)O(n^4)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png